package algorithm;

import java.util.ArrayList;
import java.util.Collections;

/*
    字符串模式匹配
 */
public class StrMatch {

    public static ArrayList<Integer> longPreSubfix;

    public static void main(String[] args) {
        String mainStr = "fafgabaaabaacawqe";
        String targetStr = "we";
        longPreSubfix = new ArrayList<>(Collections.nCopies(targetStr.length(), 0));

        //int index = match(mainStr, targetStr);
        //System.out.println(index);

        generateTable(targetStr);
        System.out.println(longPreSubfix);

        //前缀表改为next数组  向右移动并且将第一位改为-1
        longPreSubfix.remove(longPreSubfix.size() - 1);
        longPreSubfix.add(0, -1);

        Integer[] arr=new Integer[targetStr.length()];
        int index = matchKmp(mainStr, targetStr, longPreSubfix.toArray(arr));
        System.out.println(index);
    }

    public static int match(String s1, String s2) {

        int i = 0;
        int j = 0;
        while (i < s1.length() && j < s2.length()) {
            if (s1.charAt(i) == s2.charAt(j)) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }

        if (j >= s2.length()) {
            return i - s2.length();
        } else {
            return -1;
        }
    }

    //KMP
    public static int matchKmp(String s1, String s2, Integer[] next) {

        int i = 0;
        int j = 0;
        while (i < s1.length() && j < s2.length()) {
            if (j == -1 || s1.charAt(i) == s2.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }

        if (j >= s2.length()) {
            return i - s2.length();
        } else {
            return -1;
        }
    }

    //查找最长公共前后缀构建前缀表
    public static void generateTable(String s1) {
        for (int i = 1; i < s1.length(); i++) {
            String substring = s1.substring(0, i + 1); //直接从两个字符串开始遍历
            for (int j = i; j > 0; j--) {
                String s2 = substring.substring(0, j);
                String s3 = substring.substring(substring.length() - j, substring.length());
                if (s2.equals(s3)) {
                    longPreSubfix.set(i, s2.length());
                    break;
                }
            }
        }
    }
}
